/**
 * 
 */
package combinatorics;

import java.util.HashSet;
import java.util.Set;

import utils.CreateUtils;

/**
 * @author Michael
 *
 * Given n people, initially outside of a room, a function move(i) to move in/out the i-th person
 * Let the room contain every subset of the n people.
 * 
 * 5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
 * ，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
 * 中出现且仅出现一次，比如两个人，
 * 初始 {}
 * move(1): {1}
 * move{2}: {1, 2}
 * move{1}: {2}
 */
public class MoveInAndOut {
	/*
	 * people: an array of people (size = n)
	 * peopleInTheRoom: a set of people in the room
	 * index: current person to move in/out
	 * n: total number of people
	 */
	public static void subsets(Integer[] people, Set<Integer> peopleInTheRoom,
			int index, int n) {
		if (index == n) {
			for (int p : peopleInTheRoom) {
				System.out.printf("%d ", p);
			}
			System.out.println();
		}
		else {
			move(people[index], peopleInTheRoom);
			subsets(people, peopleInTheRoom, index + 1, n);
			move(people[index], peopleInTheRoom);
			subsets(people, peopleInTheRoom, index + 1, n);
		}
		
	}
	
	public static void move(Integer person, Set<Integer> peopleInTheRoom) {
		if (peopleInTheRoom.contains(person)) {
			peopleInTheRoom.remove(person);
		}
		else {
			peopleInTheRoom.add(person);
		}
	}
	
	/**
	 * 
	 */
	public MoveInAndOut() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//final int n = CreateUtils.randNonNegInt(8);
		//System.out.println(n);
		int n = 2;
		final Integer[] people = new Integer[n];
		for (int i = 0; i < n; i++)
			people[i] = new Integer(i + 1);
		subsets(people, new HashSet<Integer>(), 0, n);
	}

}
